SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

</head>

</h1>

</header>

<p>In <a href="Computing" title="Computing">computing</a>, especially <a href="Computational_geometry" title="Computational geometry">computational geometry</a>, a <b>real RAM</b> (<a href="Random-access_machine" title="Random-access machine">random-access machine</a>) is a mathematical <a href="Model_of_computation" title="Model of computation">model of a computer</a> that can compute with exact <a href="Real_number" title="Real number">real numbers</a> instead of the binary <a href="Fixed-point_arithmetic" title="Fixed-point arithmetic">fixed-point</a> or <a href="Floating-point_arithmetic" title="Floating-point arithmetic">floating-point</a> numbers used by most actual computers. The real RAM was formulated by <a href="Michael_Ian_Shamos" title="Michael Ian Shamos">Michael Ian Shamos</a> in his 1978 Ph.D. dissertation.<sup id="cite_ref-1" class="reference"><a href="#cite_note-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading2"><h2 id="Model">Model</h2></div>

<p>The "RAM" part of the real RAM model name stands for "<a href="Random-access_machine" title="Random-access machine">random-access machine</a>". This is a model of computing that resembles a simplified version of a standard computer architecture. It consists of a <a href="Stored_program" class="mw-redirect" title="Stored program">stored program</a>, a <a href="Computer_memory" title="Computer memory">computer memory</a> unit consisting of an array of cells, and a <a href="Central_processing_unit" title="Central processing unit">central processing unit</a> with a bounded number of <a href="Processor_register" title="Processor register">registers</a>. Each memory cell or register can store a real number. Under the control of the program, the real RAM can transfer real numbers between memory and registers, and perform arithmetic operations on the values stored in the registers.

</p><p>The allowed operations typically include addition, subtraction, multiplication, and division, as well as comparisons, but not modulus or rounding to integers. The reason for avoiding integer rounding and modulus operations is that allowing these operations could give the real RAM unreasonable amounts of computational power, enabling it to solve <a href="PSPACE-complete" title="PSPACE-complete">PSPACE-complete</a> problems in polynomial time.<sup id="cite_ref-2" class="reference"><a href="#cite_note-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup>

</p><p>When analyzing algorithms for the real RAM, each allowed operation is typically assumed to take <a href="Constant_time" class="mw-redirect" title="Constant time">constant time</a>.

</p>

<div class="mw-heading mw-heading2"><h2 id="Implementation">Implementation</h2></div>

<p><a href="Software_library" class="mw-redirect" title="Software library">Software libraries</a> such as <a href="Library_of_Efficient_Data_types_and_Algorithms" title="Library of Efficient Data types and Algorithms">LEDA</a> have been developed which allow programmers to write computer programs that work as if they were running on a real RAM.

These libraries represent real values using <a href="Data_structure" title="Data structure">data structures</a> which allow them to perform arithmetic and comparisons with the same results as a real RAM would produce. For example, In LEDA, real numbers are represented using the <code>leda_real</code> datatype, which supports <i>k</i>-th roots for any natural number <i>k</i>, rational operators, and comparison operators.<sup id="cite_ref-3" class="reference"><a href="#cite_note-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup> The time analysis of the underlying real RAM algorithm using these real datatypes

can be interpreted as counting the number of library calls needed by a given algorithm.<sup id="cite_ref-4" class="reference"><a href="#cite_note-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading2"><h2 id="Comparison_to_other_computational_models">Comparison to other computational models</h2></div>

<ul><li>In the <a href="Turing_machine" title="Turing machine">Turing machine</a> model, the basic unit of computation involves one bit. Therefore, the time and space complexity of numeric algorithms depends on the number of bits needed to represent the numbers. In contrast, in the Real RAM model, the basic unit of computation involves a real number, regardless of how many bits are required to represent it. This difference is important when analyzing algorithms such as <a href="Gaussian_elimination" title="Gaussian elimination">Gaussian elimination</a>: this algorithm requires a polynomial number of arithmetic operations on real numbers, so it is polynomial in the Real RAM model; however, the numbers used in the intermediate computations may (if implemented naively) grow exponentially large, so its run-time in the Turing Machine model is exponential.<sup id="cite_ref-5" class="reference"><a href="#cite_note-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup><sup class="reference nowrap"><span title="Location: Sec.1.4">: Sec.1.4 </span></sup></li>

<li>The real RAM closely resembles the later <a href="Blum%E2%80%93Shub%E2%80%93Smale_machine" title="Blum–Shub–Smale machine">Blum–Shub–Smale machine</a>.<sup id="cite_ref-6" class="reference"><a href="#cite_note-6"><span class="cite-bracket">[</span>6<span class="cite-bracket">]</span></a></sup> However, the real RAM is typically used for the analysis of concrete algorithms in <a href="Computational_geometry" title="Computational geometry">computational geometry</a>, while the Blum–Shub–Smale machine instead forms the basis for extensions of the theory of <a href="NP-completeness" title="NP-completeness">NP-completeness</a> to real-number computation.</li>

<li>An alternative to the real RAM is the <a href="Word_RAM" title="Word RAM">word RAM</a>, in which both the inputs to a problem and the values stored in memory and registers are assumed to be integers with a fixed number of bits. The word RAM model can perform some operations more quickly than the real RAM; for instance, it allows fast <a href="Integer_sorting" title="Integer sorting">integer sorting</a> algorithms, while sorting on the real RAM must be done with slower <a href="Comparison_sort" title="Comparison sort">comparison sorting</a> algorithms. However, some computational geometry problems have inputs or outputs that cannot be represented exactly using integer coordinates; see for instance the <a href="Perles_configuration" title="Perles configuration">Perles configuration</a>, an arrangement of points and line segments that has no integer-coordinate representation.</li></ul>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFShamos1978" class="citation cs2"><a href="Michael_Ian_Shamos" title="Michael Ian Shamos">Shamos, Michael Ian</a> (1978), <i>Computational Geometry</i>, Ph.D. dissertation, Yale University</cite>.</span>

</li>

<li id="cite_note-2"><span class="mw-cite-backlink"><b><a href="#cite_ref-2">^</a></b></span> <span class="reference-text"><cite id="CITEREFSchönhage1979" class="citation cs2"><a href="Arnold_Sch%C3%B6nhage" title="Arnold Schönhage">Schönhage, Arnold</a> (1979), "On the power of random access machines", <a href="International_Colloquium_on_Automata%2C_Languages_and_Programming" title="International Colloquium on Automata, Languages and Programming"><i>Proceedings of the Sixth International Colloquium on Automata, Languages and Programming (ICALP '79)</i></a>, <a href="Lecture_Notes_in_Computer_Science" title="Lecture Notes in Computer Science">Lecture Notes in Computer Science</a>, vol. 71, Springer, pp. <span class="nowrap">520–</span>529, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F3-540-09510-1_42">10.1007/3-540-09510-1_42</a>, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-540-09510-1</bdi>, <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=0573259">0573259</a></cite>.</span>

</li>

<li id="cite_note-3"><span class="mw-cite-backlink"><b><a href="#cite_ref-3">^</a></b></span> <span class="reference-text"><cite id="CITEREFMelhornNäher1999" class="citation book cs1">Melhorn, Kurt; Näher, Stefan (1999). <a rel="nofollow" class="external text" href="https://people.mpi-inf.mpg.de/~mehlhorn/LEDAbook.html"><i>The LEDA Platform of Combinatorial and Geometric Computing</i></a>. Cambridge University Press<span class="reference-accessdate">. Retrieved <span class="nowrap">12 November</span> 2019</span>.</cite></span>

</li>

<li id="cite_note-4"><span class="mw-cite-backlink"><b><a href="#cite_ref-4">^</a></b></span> <span class="reference-text"><cite id="CITEREFMehlhornSchirra2001" class="citation cs2"><a href="Kurt_Mehlhorn" title="Kurt Mehlhorn">Mehlhorn, Kurt</a>; Schirra, Stefan (2001), <a rel="nofollow" class="external text" href="http://www.mpi-inf.mpg.de/~mehlhorn/ftp/leda_real_TGA.pdf">"Exact computation with <code>leda_real</code>—theory and geometric applications"</a> <span class="cs1-format">(PDF)</span>, <i>Symbolic Algebraic Methods and Verification Methods (Dagstuhl, 1999)</i>, Springer, pp. <span class="nowrap">163–</span>172, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F978-3-7091-6280-4_16">10.1007/978-3-7091-6280-4_16</a>, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-211-83593-7</bdi>, <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=1832422">1832422</a></cite>.</span>

</li>

<li id="cite_note-5"><span class="mw-cite-backlink"><b><a href="#cite_ref-5">^</a></b></span> <span class="reference-text"><cite id="CITEREFGrötschelLovászSchrijver1981" class="citation journal cs1">Grötschel, M.; Lovász, L.; Schrijver, A. (1981-06-01). <span class="id-lock-subscription" title="Paid subscription required"><a rel="nofollow" class="external text" href="https://doi.org/10.1007/BF02579273">"The ellipsoid method and its consequences in combinatorial optimization"</a></span>. <i>Combinatorica</i>. <b>1</b> (2): <span class="nowrap">169–</span>197. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2FBF02579273">10.1007/BF02579273</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/1439-6912">1439-6912</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:43787103">43787103</a>.</cite></span>

</li>

<li id="cite_note-6"><span class="mw-cite-backlink"><b><a href="#cite_ref-6">^</a></b></span> <span class="reference-text"><cite id="CITEREFBlumShubSmale1989" class="citation cs2"><a href="Lenore_Blum" title="Lenore Blum">Blum, Lenore</a>; <a href="Michael_Shub" title="Michael Shub">Shub, Mike</a>; <a href="Stephen_Smale" title="Stephen Smale">Smale, Steve</a> (1989), "On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions and universal machines", <i><a href="Bulletin_of_the_American_Mathematical_Society" title="Bulletin of the American Mathematical Society">Bulletin of the American Mathematical Society</a></i>, <b>21</b> (1): <span class="nowrap">1–</span>46, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://doi.org/10.1090%2FS0273-0979-1989-15750-9">10.1090/S0273-0979-1989-15750-9</a></span>, <a href="Zbl_(identifier)" class="mw-redirect" title="Zbl (identifier)">Zbl</a> <a rel="nofollow" class="external text" href="https://zbmath.org/?format=complete&q=an:0681.03020">0681.03020</a></cite>.</span>

</li>

</ol></div></div>

<div class="mw-heading mw-heading2"><h2 id="External_links">External links</h2></div>

<ul><li><a rel="nofollow" class="external text" href="http://www.sciencedirect.com/science/article/pii/S0885064X98904885">Feasible Real Random Access Machines References</a></li>

<li><a rel="nofollow" class="external text" href="http://www.mpi-inf.mpg.de/~mehlhorn/ftp/SoCG09.pdf">Geometric Computing The Science of Making Geometric Algorithms Work</a></li></ul></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-06-19" href="https://en.wikipedia.org/wiki/?title=Real_RAM&oldid=1296419369">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>